package _08_DFS_BFS;

import java.util.ArrayList;
import java.util.List;

public class _797_所有可能的路径 {

    private List<List<Integer>> results = new ArrayList<>();

    public static void main(String[] args) {
        _797_所有可能的路径 v = new _797_所有可能的路径();
        int[][] ins = new int[][]{
                {1, 2},
                {3},
                {3},
                {}
        };
        List<List<Integer>> lists = v.allPathsSourceTarget(ins);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
    }

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(0);
        dfs(graph, 0, list);
        return results;
    }

    private void dfs(int[][] graph, int i, List<Integer> store) {
        if (i == graph.length - 1) {
            results.add(new ArrayList<>(store));
            return;
        }
        int[] list = graph[i];
        for (int cur : list) {
            store.add(cur);
            dfs(graph, cur, store);
            // 回溯, 移出最后一个元素
            store.remove(store.size() - 1);
        }
    }

}
